For safety purpose, intelligent video surveillance system is developed rapidly in recent years. There have been many surveillance systems applied to our surrounding environments, such as airports, train stations, shopping malls, and even private residential areas where tight or great security is required. Among those, the intelligent video surveillance systems are roughly classified into two levels. Low-level intelligent video surveillance system can detect features of objects in the image frames. The data obtained by the low-level intelligent video surveillance system can be further processed by high-level intelligent video surveillance system to monitor various events in real time, e.g. motion detection.
One typical approach for motion detection is background subtraction. Background subtraction refers to a robust background model. A binary mask obtained by an adaptive background subtraction specifies whether a pixel belongs to the background or foreground. The foreground pixels are analyzed to get connected components. Connected component labeling algorithm is advantageous to estimate the total number of the objects in the binary mask by means of grouping connected pixels and assigning a unique label for connected pixels.
A basic forward scan procedure in the connected component labeling algorithm is described with reference to FIG. 1. The binary mask 100 is scanned from left to right and top to bottom as denoted by the arrow 101. That is, the pixels are scanned in the order from a to i. During the forward scan procedure, each foreground pixel is assigned a label. For example, when the forward scan procedure reaches pixel e, the previous pixels a˜d (called as “reference neighbor pixels” hereinafter) have been scanned and assigned a corresponding label. The smallest one of the labels assigned to the L-shape reference neighbor pixels (and the label assigned to the current pixel in a previous scan procedure, if any) is assigned to the current pixel e. If none of the reference neighbor pixels is foreground pixel and the current pixel receives no label, a new label is assigned to the current pixel e. By repeating the step, each foreground pixel receives a label after the forward scan procedure.
The forward scan procedure is applied to several connected component labeling algorithm, e.g. multi-pass algorithm and two-pass algorithm. In the multi-pass algorithm, the forward scan procedure and a backward scan procedure are alternatively performed until there are no changes in labels. Backward scan procedure scans in a reverse direction to the forward scan procedure, i.e. from right to left and bottom to top. Therefore, the reference neighbor pixels of current pixel e are pixels f˜i. The drawback of multi-pass algorithm is terribly large number of passes. Someone proposes using a label connection table to reduce the number of scans. However, the iteration still consumes great amount of resources due to continuous reading the label information of the whole image. Furthermore, the number of assigned labels cannot be reduced effectively during the scan procedures.
Two-pass algorithm generally operates in three phases. At first, in the scanning phase, the image is scanned once to assign provisional labels to all foreground pixels, and the label equivalence information about the provisional labels is recorded. Then, in an analysis phase, the label equivalence information is analyzed to determine the final label of each foreground pixel. At last, in a labeling phase, the final labels are assigned in a second pass (scan) through the image. In practice, the analysis phase may be integrated into the other two. Although the two-pass algorithm required only two scans, too many assigned labels together with the label connection table recording the relations of assigned labels occupy memory and exhaust the label supply of hardware, especially when too much noise is included.
Therefore, there is a need of providing an efficient connected component labeling algorithm requiring less hardware resource to obviate the drawbacks encountered from the prior art.